package list;

import java.util.HashSet;
import java.util.Set;

/**题目：单链表中环的开始节点
 * @Author Gavin
 * @date 2022.01.23 16:49
 */
public class list_12 {
    /**
     * 解题思路：
     * 第一种，使用一个set集合来处理，遍历每一个节点，然后把每个节点值
     * 存入到set中，如果set中包含了这个节点那么这个节点就是环的节点直接返回
     */
    //Time:O(n) Space:O(n)
    public ListNode solution_1(ListNode head){
        Set<ListNode> set=new HashSet<>();
        for (ListNode p=head;p!=null;p=p.next){
            if(set.contains(p))return p;
            set.add(p);
        }
        return null;
    }
    /**
     * 第二种思路：
     * 使用快慢指针来处理
     */
    public ListNode solution_2(ListNode head){
        ListNode fast=head,slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                for (ListNode p=head;p!=slow;p=p.next,slow=slow.next);
                return slow;
            }
        }
        return null;
    }
}
